package com.test.sort;

import java.util.Arrays;

/**
 * https://www.cnblogs.com/xiaochun126/p/5086037.html
 * 1、时间复杂度
 *
 *      时间复杂度可以认为是对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
 *
 *      常见的时间复杂度有：常数阶O(1),对数阶O(log2n),线性阶O(n), 线性对数阶O(nlog2n),平方阶O(n2)
 *
 *      时间复杂度O(1)：算法中语句执行次数为一个常数，则时间复杂度为O(1),
 *
 * 2、空间复杂度
 *
 *     空间复杂度是指算法在计算机内执行时所需存储空间的度量，它也是问题规模n的函数
 *
 *     空间复杂度O(1)：当一个算法的空间复杂度为一个常量，即不随被处理数据量n的大小而改变时，可表示为O(1)
 *
 *     空间复杂度O(log2N)：当一个算法的空间复杂度与以2为底的n的对数成正比时，可表示为O(log2n)
 *
 *                                  ax=N，则x=logaN，
 *
 *     空间复杂度O(n)：当一个算法的空间复杂度与n成线性比例关系时，可表示为0(n).
 */
public class ShellSort extends BaseSort{
    //希尔排序
    public static void main(String[] args) {
        //1纳秒=0.000001 毫秒=10的负6次方毫秒
        //一秒的10亿分之一，即等于10的负9次方秒。常用作 内存读写速度的单位
        long start = System.nanoTime();
        BaseSort sort = new ShellSort();
        int[] a = {8, 2, 1, 6, 3, 9, 5, 7, 23, 13,27};
        sort.sort(a);
        long end = System.nanoTime();
        System.err.println((end-start)+"纳秒");
        Arrays.stream(a).forEach(System.out::println);
    }

    /**
     * 希尔排序(Shell Sort)是插入排序的一种算法，是对直接插入排序的一个优化，也称缩小增量排序。
     * 希尔排序是非稳定排序算法。
     *
     * 希尔排序
     * 把数组分割成若干(h)个小组(一般数组长度length/2)，然后对每一个小组分别进行插入排序。
     * 每一轮分割的数组的个数逐步缩小，h/2->h/4->h/8，并且进行排序，保证有序。
     * 当h=1时，则数组排序完成
     *
     * 平均时间复杂度：O(nlog2n)  使用了while-for-while
     *        O(nlog2n) = O(n) * O(log2N) 即既有线性比例关系，又有对数比例关系
     *
     *
     * 算法空间复杂度：O(1)
     * 算法稳定性：稳定
     *
     *
     * @param nums
     */
    @Override
    protected void sort(int[] nums) {
        if (nums == null || nums.length < 2) {
            return;
        }
        int length = nums.length;
        int temp;
        //步长
        int gap = length / 2;
        while (gap > 0) {
            for (int i = gap; i < length; i++) {
                temp = nums[i];
                int preIndex = i - gap;
                while (preIndex >= 0 && nums[preIndex] > temp) {
                    nums[preIndex + gap] = nums[preIndex];
                    preIndex -= gap;
                }
                nums[preIndex + gap] = temp;
            }
            gap /= 2;
        }
    }
}
